package unionfindset.Solution;

import java.util.Arrays;

public class Solution {
    //省份数量
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFindSet ufs = new UnionFindSet(n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(isConnected[i][j] == 1) {
                    ufs.union(i, j);//合并
                }
            }
        }
        //遍历找出-1的个数
        return ufs.getCount();
    }
    //2.等式方程的可满足性(并查集)
    public boolean equationsPossible(String[] equations) {
        UnionFindSet ufs = new UnionFindSet(26);//26个字母
        for(int i = 0; i < equations.length; i++) {
            if(equations[i].charAt(1) == '=') {
                ufs.union(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a');
            } else {

            }
        }
        for(int i = 0; i < equations.length; i++) {
            if(equations[i].charAt(1) == '!') {
                int index1 = ufs.findRoot(equations[i].charAt(0) - 'a');
                int index2 = ufs.findRoot(equations[i].charAt(3) - 'a');
                if(index1 == index2) {//这里时不等于的情况，等于了就有问题
                    return false;
                }
            }
        }
        return true;
    }
}
class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem, -1);
    }

    /**
     * 查找数组 x下标是否是根节点
     * @param x
     * @return
     */
    public int findRoot(int x) {
        if(x < 0) {
            throw new IndexOutOfBoundsException("下表不合法，是负数");
        }
        while(elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    /**
     * 查询 x1 和 x2 是不是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1, int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        return index1 == index2;//跟结点是否相同
    }

    /**
     * 合并操作
     * @param x1
     * @param x2
     */
    public void union(int x1, int x2) {
        //先找到 x1, x2 的根节点
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            return;
        }
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;
    }

    /**
     * 集合个数
     * @return
     */
    public int getCount() {
        int count = 0;
        for(int x : elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }
}
